#include<iostream>
using namespace std;
struct data_str
{
	int weight;                                    //权值
	int next;                                      //下一节点
	int day;                                       //已花天数
};
data_str N1[30][30];                               
int FMultiGraph(int k,int*p,int n)	     
{   
    float *cost=new float[n]; 
    int   *dry=new int[n];        
    int   *cod=new int[n];		  
    for(int i=0;i<n;i++)	cost[i]=0;
    for (int j=0;j<=n-1;j++) 	
		for (int r=0;r<sizeof(N1[j]);r++) 
			if (N1[j][r].weight+cost[j]>cost[N1[j][r].next])                    //获得学分更高
			{
				cost[N1[j][r].next]=N1[j][r].weight+cost[j];                    //记录最大值
				dry[N1[j][r].next]=j;			
				cod[N1[j][r].next]=N1[j][r].day;
			}
    int answer=cost[n-1]; 	
    int tem=n-1;
    for(int i=k;i>0;i--) 
    {
    	p[i]=cod[tem];
    	tem=dry[tem];
	}
    delete []cost;
    delete []dry;
    delete []cod;
    return answer;
}
int main()
{
	int k=5;
	int n=18;
	int p[200];
	int w[4][4]={4,4,5,8,                                //将每个边的权值直接给出
			  	 3,5,6,7,
				 5,6,8,8,
				 2,4,7,8
				 };
	for(int i=1;i<5;i++)
	{
		data_str temp={w[0][i-1],i,i};
		N1[0][0]=temp;
	}
	int now_num=0;
	for(int i=0;i<3;i++)
		for(int j=1;j<=4;j++)
			for(int k=j;k<=4;k++)
			{
				data_str temp={w[i+1][k-j],i*4+j+k-j+4,k-j+1};
				N1[i*4+j][k+i*j]=temp;
			}
	for(int i=13;i<17;i++)
	{
		data_str temp={0,17,0};
		N1[i][i]=temp ;
	}

	cout<<"获得的最高学分为："<<FMultiGraph(k,p,n)<<endl;
	cout<<"获得最高学分的方法如下："<<endl;
	for(int i=1;i<k;i++)
		cout<<"第"<<i<<"阶段使用"<<p[i]<<"天"<<endl; 
	return 0;
}